Міністерство освіти і науки України
Національний університет ″Львівська політехніка″
Звіт
про виконання лабораторної роботи №2
з курсу “ АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ ”
на тему: “ ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ ”
Мета роботи: вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері; дослідити швидкодію алгоритмів множення довгих чисел.
Завдання:
Домашня підготовка до роботи
1) Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами.
2) Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур’є) або ділення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться з лабораторної роботи №1. Дані для роботи беруться за вказівкою викладача.
3) Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 50 до 200. Накреслити графіки відповідних залежностей і порівняти одержані результати.
№
з/п
Операції з довгими числами
2
Швидке множення
Робота в лабораторії
1) Ввести в комп'ютер програми згідно з отриманим завданням.
2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками.
3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи.
4) Здати звіт з лабораторної роботи.
Блок-схема алгоритму швидкого множення
Список ідентифікаторів констант, змінних і функцій, використаних у
головній програмі і підпрограмах , та їх пояснення
MaxDigit – константа що вказує на максимальну довжину масиву;
Osn – константа що вказує на основу;
Input() ввід довгого числа з клавіатури;
Output() вивід довгого числа на екран;
FastMul ()швидке множення двох довгих чисел ;
a[] – массив, що представляє довге число, множник;
b[]– массив, що представляє довге число, множник;
c[]– массив, що представляє довге число, результат;
i, j, k – цілі змінні, що використовуються в циклі.
Остаточна версія програми
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 100
#define OSN 10000
void InputNum(const char *str, long a[MAX_LEN])
{
int j,i=strlen(str);
char *tmp=(char*)malloc(i+1);
strcpy(tmp, str); j=0;
do
{
tmp[i]=0; i-=4; if(i<0) i=0;
sscanf(&tmp[i], "%ld", &a[MAX_LEN - ++j]);
} while (i);
while (j<MAX_LEN) a[MAX_LEN - ++j]=-1;
free(tmp);
}
void OutputNum(long a[MAX_LEN])
{
int i,fn=0;
while (fn<MAX_LEN && a[fn]==-1) fn++;
if(fn==MAX_LEN) return;
for (i=fn;i<MAX_LEN; i++)
printf((i==fn) ? "%d" : "%04d", a[i]);
}
int Less(long a[MAX_LEN], long b[MAX_LEN])
{
int i=-1;
while (++i<MAX_LEN)
if (a[i]==b[i]) continue;
else return a[i]<b[i] ? 1 : -1;
return 0;
}
int FindFirstNum(const long a[MAX_LEN])
{
int ret=MAX_LEN-1; while(a[ret]!=-1 && ret>=0) ret--; return ret+1;
}
void Div2(long a[MAX_LEN])
{
long i, fAdd=0, tmp, fNum;
fNum = FindFirstNum(a);
for(i = fNum; i<MAX_LEN; ++i)
{
tmp=a[i]+fAdd;
fAdd = (tmp & 1) ? OSN : 0;
tmp>>=1; if(tmp==0 && i==fNum && i!=MAX_LEN-1) {a[i]=-1; continue;}
a[i] = tmp;
}
}
void Mul2(long a[MAX_LEN])
{
int i=MAX_LEN; long fAdd=0,tmp;
while(a[--i]!=-1)
{
tmp=a[i]; tmp=(tmp<<1) + fAdd; fAdd=0;
if(tmp>=OSN) fAdd=1, tmp-=OSN;
a[i]=tmp;
}
if(fAdd) a[i]=fAdd, a[i-1]=-1;
}
void AddToNum(long a[MAX_LEN], const long b[MAX_LEN])
{
int to,i,j; long tmp,ta,tb,fAdd=0;
i = FindFirstNum(a), j = FindFirstNum(b);
to = (i>j) ? j : i;
for (i=MAX_LEN-1; i>=to; --i)
{
ta=a[i]; if(ta<0) ta=0;
tb=b[i]; if(tb<0) tb=0;
tmp = ta+tb+fAdd; fAdd=0;
if(tmp>=OSN) fAdd=1, tmp-=OSN;
a[i]=tmp;
}
if(fAdd) a[i]=fAdd, a[i-1]=-1;
}
void FastMul(long ta[MAX_LEN], long tb[MAX_LEN], long c[MAX_LEN])
{
long *a,...
